package 牛客网在线编程题库;

/**
 * 题目描述
 给出两个有序的整数数组A和B，请将数组B合并到数组A中，变成一个有序的数组
 注意：
 可以假设A数组有足够的空间存放B数组的元素，A和B中初始的元素数目分别为m和n
 */

public class _合并两个有序的数组 {
    public static void main(String[] args) {

    }

    /**
     * 双指针法
     * @param A
     * @param m
     * @param B
     * @param n
     */
    public static void merge(int A[], int m, int B[], int n) {
        // 当n为0时，不需要合并
        if (n == 0) {
            return;
        }
        // 当m为0时，并且n不为0，需要将B拷贝到A
        else if (m == 0) {
            for (int i = 0 ; i < n ; i++) {
                A[i] = B[i];
            }
            return;
        }
        // 当两数组都为0，不做操作
        if (m == 0 && n == 0) {
            return;
        }
        // 双指针法从后往前遍历
        // 循环直到其中一条链表遍历完毕
        while (m > 0 && n > 0) {
            if (A[m - 1] >= B[n - 1]) {
                // 将大的元素直接放到该放的位置
                A[m + n - 1] = A[m - 1];
                m--;
            }else {
                A[m + n - 1] = B[n - 1];
                n--;
            }
        }
        // A指针遍历完毕，但是B还未结束
        for (int i = 0 ; i < n ; i++) {
            A[i] = B[i];
        }
    }
}
